package cxydmmszl.chapter04.t073;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 排成一条线的纸牌博弈问题
 * <li style="color: green;">Desc</li>
 * 给定一个整型数组 arr，代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，
 * 规定玩家 A 先拿，玩家 B 后拿，但是每个玩家每次只能拿走最左和最右的纸牌，玩家 A 和玩家 B 绝顶聪明。
 * 请返回最后的获胜者的分数。
 * <li style="color: green;">Input</li>
 * 输出包含两行，第一行一个整数 n(1<=n<=5000)，代表数组 arr 的长度，
 * 第二行包含 n 个整数，第 i 个代表 arr[i](1<=arr[i]<=10^5)。
 * <li style="color: green;">Output</li>
 * 输出一个整数，代表最后获胜者的分数。
 * <li style="color: blue;">Link</li> CD91
 *
 * @author habitplus
 * @since 2021-09-23 09:39
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] ss = br.readLine().split(" ");
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(ss[i]);
        }
        br.close();

        int ans = win2(arr);
        System.out.println(ans);
    }

    private static int win2(int[] arr) {
        if (arr == null || arr.length == 0) return 0;

        // 动态规划：
        // first[i][j] 表示 arr[i...j] 这个排列上的纸牌被绝顶聪明的人先拿，最终能获得什么分数。
        // after[i][j] 表示 arr[i...j] 这个排列上的纸牌被绝顶聪明的人后拿，最终能获得什么分数。
        // first[i][j] = max(arr[i] + after[i+1][j], arr[j] + after[i][j-1])
        // after[i][j] = min(first[i+1][j], first[i][j-1])
        int n = arr.length;
        int[][] first = new int[n][n];
        int[][] after = new int[n][n];

        for (int j = 0; j < n; j++) {
            // 只有一张牌时，先拿的人直接取，后拿的人没有牌可以拿
            first[j][j] = arr[j];

            for (int i = j - 1; i >= 0; i--) {
                first[i][j] = Math.max(arr[i] + after[i + 1][j], arr[j] + after[i][j - 1]);
                after[i][j] = Math.min(first[i][j - 1], first[i + 1][j]);
            }
        }
        return Math.max(first[0][n - 1], after[0][n - 1]);
    }
}
